package notes.java.sort;

/**
 * 计数排序
 * 1、定义一个新数组长度为原数组中最大数加1（含0情况），遍历原数组，第1个元素是n就在新数组下标为n的位置记录1
 * 2、当遍历数组时再有n时，n下标所在值就+1，直到遍历完数组，新数组计数完毕
 * 3、遍历新数组，根据计数的值，是多少就输出多少个下标数，就是排序最终的数组
 *
 */
public class S7_CountSort {
	
	public static void main(String[] args) {
		
		// 定义一个数组（9以内的，最大数9）
		int arr[] = {3, 4, 1, 2, 1, 3, 5, 8, 0, 2, 4, 6, 7, 9, 3};
		
		
		// 定义一个计数新数组，大小为原数组的最大数加1
		int countArr[] = new int[10];
		
		// 遍历，并计数
		for(int i=0; i<arr.length; i++) {
			countArr[arr[i]] ++;
		}
		
		print(countArr);
		
		// 最终输入的数组
		int resultArr[] = new int[arr.length];
		
		// 遍历计数数组
		for(int i=0, j=0; i<countArr.length; i++) {
			while(countArr[i]-->0) {
				resultArr[j++] = i;
			}
		}
		

		
		print(resultArr);
	}

	
	/** 打印输出*/
	private static void print(int[] num) {
		// 输出
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
	}
}
